Počet bodov: 30, časový limit: 2000ms
Vyčerpaný Martin sa rozhodol, že na ďalšej hodine zamestná žiakov a on si bude mať čas poriadne oddýchnuť od všetkého toho triedenia. Prichystal im preto zopár veľmi pekných príkladov za bonusové body. Tieto príklady boli špecifické hneď dvoma vlastnosťami:
Hneď na začiatku hodiny im ich všetky napísal na tabuľu, vyložil si na stôl nohy a pozeral na ich sprvu bezradné tváre. Vzápätí mu však študenti začali nosiť podpísané papiere s výsledkami, a tak rýchlo oznámil, že body dostane iba prvých k ľudí na príklad. Samozrejme, nie každý vedel vypočítať všetky príklady a tak mu výsledky nosili po jednom. Prekvapený Martin zrazu bezradne pozeral na haldu papierov vo svojich rukách. Vytriediť nesprávne výsledky ešte zvládal, ale rozhodnúť, komu body udeliť a komu už nie, musíte veru vy.
Na prvom riadku vstupu bude číslo \(k\) (počet ľudí, kt. dostanú +1 bod za jeden príklad). Nasledujúci riadok bude obsahovať \(n\) čísel oddelených medzerou (\(1 \leq n \leq 10^6\)). Toto číslo neviete dopredu, veľmi ťažko sa totiž počíta počet papierov na kope, keď je ich veľa. Navyše môžete predpokladať, že pre všetky tieto čísla platí \(0 \leq |a_i| \leq 10^6\). Nech \(b_i\) je počet takých \(j<i\), že \(a_i = a_j\). Vypíšte jeden riadok so všetkými \(a_i\), pre ktoré \(b_i < k\) (teda vynechajte čísla, ktoré sú na vstupe viac ako \(k\)-ty krát).
Pozor, časový limit v tejto úlohe je veľmi prísny, riešenia písané v pomalších jazykoch v podstate nemajú šancu. V C++ odporúčame vyhýbať sa načítavaniu a vypisovaniu pomocou cin
a cout
.
Input:
1
2 4 1 2 3 4 5
Output:
2 4 1 3 5
Input:
2
9 47 -47 47 -47 9 2 9 47 -4247
Output:
9 47 -47 47 -47 9 2 -4247